import java.util.ArrayList;
import java.util.List;

/**
 * @author LKQ
 * @date 2022/2/19 19:03
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] matrix = {{1,2,3,4},{5,6,7,8},{9,10,11,12}};
        solution.spiralOrder(matrix);
    }
    /**
     * 右下左上
      */
    int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        // 已遍历个数
        int num = 0, next = 0;
        List<Integer> list = new ArrayList<>();
        boolean[][] visited = new boolean[m][n];
        int i = 0, j = 0;
        while (num < m * n) {
            list.add(matrix[i][j]);
            visited[i][j] = true;
            int ni = i + dirs[next][0], nj = j + dirs[next][1];
            if (ni >= m || ni < 0 || nj >= n || nj < 0 || visited[ni][nj]) {
                next = (next + 1) % 4;
            }
            i += dirs[next][0];
            j += dirs[next][1];
            num++;
        }
        return list;
    }
}
